package class26;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class OneMatrix {

    public static int oneMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }

        int rowN = matrix.length;
        int colN = matrix[0].length;
        int[][] row = new int[rowN][colN];
        int[][] col = new int[rowN][colN];

        generateRowArr(matrix, row, rowN - 1, colN - 1);
        generateColArr(matrix, col, rowN - 1, colN - 1);

        int max = 1;
        for (int i = 0; i < rowN; i++) {
            for (int j = 0; j < colN; j++) {
                for (int k = 1; k +i-1  < rowN && k+j-1<colN; k++) {
                    if (isV(row, col, i, j, k)) {
                        max = Math.max(max, k);
                    }
                }
            }
        }

        return max;
    }

    private static boolean isV(int[][] row, int[][] col, int i, int j, int k) {
        int rowL = row[i][j];
        int colL = col[i][j];
        int rowLK = row[i + k-1][j];
        int colLK = col[i][j + k-1];

        if (rowL >= k && colL >= k && rowLK >= k && colLK >= k) {
//            System.out.println("k: "+k+ " rowL: "+rowL+" colL: "+colL+" rowLK: "+rowLK+" colLK: "+colLK);
            return true;
        }
        return false;
    }

    private static void generateRowArr(int[][] matrix, int[][] r, int row, int col) {
        for (int i = 0; i <= row; i++) {
            r[i][col] = matrix[i][col] == 1 ? 1 : 0;
        }
        for (int i = 0; i <= row; i++) {
            for (int j = col - 1; j >= 0; j--) {
                r[i][j] = matrix[i][j] == 1 ? 1 + r[i][j + 1] : 0;
            }
        }

//        System.out.println("------generateRowArr-----");
//        for (int i = 0;i<=row;i++){
//            for (int j = 0;j<=col;j++){
//                System.out.print(r[i][j]+" ");
//            }
//            System.out.println();
//        }
//        System.out.println();
    }

    private static void generateColArr(int[][] matrix, int[][] c, int row, int col) {
        for (int i = 0; i <= col; i++) {
            c[row][i] = matrix[row][i] == 1 ? 1 : 0;
        }
        for (int i = row - 1; i >= 0; i--) {
            for (int j = 0; j <= col; j++) {
                c[i][j] = matrix[i][j] == 1 ? 1 + c[i + 1][j] : 0;
            }
        }

//        System.out.println("------generateColArr-----");
//        for (int i = 0;i<=row;i++){
//            for (int j = 0;j<=col;j++){
//                System.out.print(c[i][j]+" ");
//            }
//            System.out.println();
//        }
//        System.out.println();
    }

    public static void main(String[] args) {
        int[][] arr = new int[][]{
                {0, 1, 1, 1, 1},
                {0, 1, 1, 1, 1},
                {0, 1, 0, 1, 1},
                {0, 1, 1, 1, 1},
                {0, 1, 0, 0, 1}
        };

        System.out.println(oneMatrix(arr));

    }
}
